package com.dkd.day20250817;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class lc003 {
    public static void main(String[] args) {
        //128. 最长连续序列
        //已解答
        //中等
        //相关标签
        //premium lock icon
        //相关企业
        //给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
        //
        //请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
        //
        //

        int [] arr ={1,2,0,1};
        System.out.println(solve(arr));
    }

    public static int solve(int[] arr){
        //排序的时间复杂度是nlogn
        arr= Arrays.stream(arr).sorted().distinct().toArray();



        int count = 1;
        int maxLen = 0;
        for(int i = 1; i <arr.length; i++){
            if(arr[i] == arr[i-1]+1){
                count++;
            }else{
                maxLen = Math.max(maxLen, count);
                count = 1;
            }
        }

        maxLen = Math.max(maxLen, count);
        return maxLen;
    }

    public static int solve2(int[] arr){
        Set<Integer> set = new HashSet<>();

        for(int i : arr){
            set.add(i);
        }

        int ans = 0;

        for(int num : set){
            if(set.contains(num-1)) continue;

            int y = num+1;
            while(set.contains(y)){
                y++;
            }

            ans = Math.max(ans, y-num);

            if(ans*2>arr.length) break;

        }

        return ans;
    }
}
